package com.sheng.leetcode.year2022.month03.day10;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2022/03/10
 * 589. N 叉树的前序遍历
 * 给定一个 n 叉树的根节点  root ，返回 其节点值的 前序遍历 。
 *
 * n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
 *
 * 示例 1：
 *
 * 输入：root = [1,null,3,2,4,null,5,6]
 * 输出：[1,3,5,6,2,4]
 * 示例 2：
 *
 * 输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 * 输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]
 *
 * 提示：
 *
 * 节点总数在范围 [0, 104]内
 * 0 <= Node.val <= 104
 * n 叉树的高度小于或等于 1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-ary-tree-preorder-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0589 {

    @Test
    public void test01(){
        Node root = new Node(1);
        List<Node> nodeList = new ArrayList<>();
        Node node = new Node(3);
        List<Node> nodeList1 = new ArrayList<>();
        nodeList1.add(new Node(5));
        nodeList1.add(new Node(6));
        node.children = nodeList1;
        nodeList.add(node);
        nodeList.add(new Node(2));
        nodeList.add(new Node(4));
        root.children = nodeList;
        List<Integer> preorder = new Solution().preorder(root);
        System.out.println(preorder);
    }
}
class Solution {
    List<Integer> preorder = new ArrayList<>();
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return preorder;
        }
        preorder.add(root.val);
        List<Node> children = root.children;
        if (root.children != null) {
            getChildren(root.children);
        }
        return preorder;
    }

    public void getChildren(List<Node> children) {
        for (Node child : children) {
            preorder.add(child.val);
            if (child.children != null) {
                getChildren(child.children);
            }
        }
    }
}
/**
 * Definition for a Node.
 */
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int vall) {
        val = vall;
    }

    public Node(int vall, List<Node> childrenn) {
        val = vall;
        children = childrenn;
    }
};
